home *** CD-ROM | disk | FTP | other *** search
/ ADA Programming Guide / ADA Programming Guide.iso / ada_gwu / set.c < prev    next >
C/C++ Source or Header  |  1996-01-30  |  9KB  |  460 lines
  1. /*
  2.  * Copyright (C) 1985-1992  New York University
  3.  * 
  4.  * This file is part of the Ada/Ed-C system.  See the Ada/Ed README file for
  5.  * warranty (none) and distribution info and also the GNU General Public
  6.  * License for more details.
  7.  
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include "config.h"
  14. #include "set.h"
  15. #include "miscp.h"
  16. #include "setp.h"
  17.  
  18. /* body of small integer set package  */
  19. /* represent sets using tuples */
  20.  
  21. static Tuple NULL_TUPLE;
  22. static char *FREE_TUPLE = (char *)0;/* list of free (singleton) tuples */
  23.  
  24. char *set_arb(Set sp)                                            /*;set_arb*/
  25. {
  26.     /* pick arbitrary element from set */
  27.  
  28.     if ((int) sp[0] == 0) chaos("set_arb - set already empty");
  29.     return sp[1];
  30. }
  31.  
  32. Set set_copy(Set sp)                                             /*;set_copy*/
  33. {
  34.     /* make copy of set */
  35.  
  36.     return (Set) tup_copy((Tuple) sp);
  37. }
  38.  
  39. Set set_del(Set sp, char *n)                                     /*;set_del*/
  40. {
  41.     /* remove n from small set */
  42.  
  43.     int        i;
  44.     int        j, cur;
  45.  
  46.     if (tup_mem(n, (Tuple) sp) == FALSE) return (sp);        /* if not member */
  47.     cur = (int) sp[0];
  48.     for (i = 1; i <= cur; i++) {
  49.         /* here to remove, element known to be present */
  50.         if (sp[i] == n) {
  51.             for (j = i + 1; j <= cur; j++) {
  52.                 sp[i] = sp[j];
  53.                 i++;
  54.             }
  55.             sp[0] = (char *) --cur;
  56.         }
  57.     }
  58.     return (sp);
  59. }
  60.  
  61. void set_free(Set sp)                                            /*;set_free*/
  62. {
  63.     /* free set */
  64.     tup_free(sp);
  65. }
  66.  
  67. char   *set_from(Set sp)                                        /*;set_from*/
  68. {
  69.     int n;
  70.  
  71.     if (sp[0] == 0) chaos("set_from null_set");
  72.     n = (int) sp[0];
  73.     sp[0] = (char *) (n-1);
  74.     return sp[n];
  75. }
  76.  
  77. Set set_less(Set s, char *n)                                    /*;set_less*/
  78. {
  79.     int    i, j, cur;
  80.  
  81.     if (!tup_mem(n, s)) return s;
  82.     cur = (int) s[0];
  83.     for (i = 1; i <= cur; i++) {
  84.         if (s[i] == n) { /* move down remaining elements */
  85.             for (j = i+1; j <= cur; j++)
  86.                 s[j-1] = s[j];
  87.             s[0] = (char *) (--cur);  /* adjust count */
  88.             return s;
  89.         }
  90.     }
  91. }
  92.  
  93. Set set_new(int n)                                                /*;set_new*/
  94. {
  95.     /* allocate new set with room for n elements */
  96.  
  97.     Set sp;
  98.  
  99.     sp = tup_new(n);
  100.     sp[0] = (char *)0;
  101.     return sp;
  102. }
  103.  
  104. Set set_new1(char *n)                                            /*;set_new1*/
  105. {
  106.     Set sp;
  107.  
  108.     sp = set_new(1);
  109.     sp = set_with(sp, n);
  110.     return sp;
  111. }
  112.  
  113.  
  114. int    set_mem(char *n, Set sp)                                    /*;set_mem*/
  115. {
  116.     /* test if n in small set sp */
  117.     return tup_mem(n, sp);
  118. }
  119.  
  120. #ifndef EXPORT
  121. int    set_size(Set sp)                                            /*;set_size*/
  122. {
  123.     /* return number of elements in small set */
  124.     return (int) sp[0];
  125. }
  126. #endif
  127.  
  128. int set_subset(Set sp1, Set sp2)                                /*;set_subset*/
  129. {
  130.     /* test for subset by just seeing if each element in first set is
  131.      * contained in the second. A better algorithm would exploit the
  132.      * ordering of the elements.
  133.      */
  134.     Forset    fs1;
  135.     char    *elem;
  136.     FORSET(elem=(char *), sp1, fs1);
  137.         if (!set_mem(elem, sp2)) return FALSE;
  138.     ENDFORSET(fs1);
  139.     return TRUE;
  140. }
  141.  
  142. Set set_union(Set sp1, Set sp2)                                    /*;set_union*/
  143. {
  144.     /* union of two small sets */
  145.  
  146.     Set t;
  147.     Set spr;
  148.     int        i, cur, n1, n2;
  149.  
  150.     /* arrange so sp1 points to larger set */
  151.     n1 = (int) sp1[0];
  152.     n2 = (int) sp2[0];
  153.     if (n2 > n1) {
  154.         /* second is larger, swap pointers */
  155.         t = sp1;
  156.         sp1 = sp2;
  157.         sp2 = t;
  158.     }
  159.     spr = set_copy(sp1);
  160.     cur = (int) sp2[0];
  161.     for (i = 1; i <= cur; i++)
  162.         spr = set_with(spr, sp2[i]);
  163.     return spr;
  164. }
  165.  
  166. Set set_with(Set sp, char *n)                                    /*;set_with*/
  167. {
  168.     /* insert n into set sp */
  169.  
  170.     unsigned cur;
  171.  
  172.     if (tup_mem(n, sp) == TRUE) return sp;        /* if already present */
  173.     cur = (unsigned) sp[0];
  174.     sp = tup_exp(sp, (unsigned)  (cur+1));
  175.     /* insert new value at end */
  176.     sp[++cur] = n;
  177.     sp[0] = (char *) cur;
  178.     return sp;
  179. }
  180.  
  181. /* Tuple operations */
  182.  
  183. void tup_init()                                                /*;tup_init*/
  184. {
  185.     /* initialize NULL_TUPLE, the (unique) null tuple */
  186.     NULL_TUPLE = (Tuple) emalloct(sizeof(char *), "null-tuple");
  187.     *NULL_TUPLE = (char *)0; /* set null length */
  188. }
  189.  
  190. Tuple tup_add(Tuple tpa, Tuple tpb)                /*;tup_add*/
  191. {
  192.     /* concatenate two tuples */
  193.  
  194.     Tuple trp;
  195.     int        i, ni = 1;
  196.  
  197.     if (tpa == (Tuple)0 ) chaos(" tup_add: first tuple null");
  198.     if (tpb == (Tuple)0 ) chaos(" tup_add: second tuple null");
  199.  
  200.     trp = tup_new(tup_size(tpa) + tup_size(tpb));
  201.     for (i = 1; i <= (int) tpa[0]; i++)
  202.         trp[ni++] = tpa[i];
  203.     for (i = 1; i <= (int) tpb[0]; i++)
  204.         trp[ni++] = tpb[i];
  205.     return trp;
  206. }
  207.  
  208. Tuple tup_copy(Tuple tp)                                        /*;tup_copy*/
  209. {
  210.     /* return copy of tuple */
  211.  
  212.     Tuple  tnp;
  213.     int        i;
  214.  
  215.     if (tp == NULL_TUPLE) return NULL_TUPLE; /* copy of null tuple is itself*/
  216.     tnp = tup_new(tup_size(tp));
  217.  
  218.     for (i = 1; i <= (int) tp[0]; i++)
  219.         tnp[i] = tp[i];
  220.     return tnp;
  221. }
  222.  
  223. Tuple tup_exp(Tuple tp, unsigned int n)                            /*;tup_exp*/
  224. {
  225.     /* expand tuple so can hold n elements */
  226.  
  227.     unsigned int oldn;
  228.     Tuple oldtp;
  229.  
  230. #ifdef CHAOS
  231.     if (n == 0 || n>99999) chaos("tup_exp: new length > 99999");
  232. #endif
  233. #ifdef SKIP
  234.     if ((int)tp[0]>n) {
  235.         /* adjust length */
  236.         tp[0] = (char *) n;
  237.         return tp;
  238.     }
  239. #endif
  240.     /* if expanding null tuple, allocate real tuple */
  241.     if (tp == NULL_TUPLE)
  242.         tp = tup_new((int)n); 
  243.     /* if expanding smalloc singleton */
  244.     else if (is_smalloc_block((char *)tp)) { 
  245.         oldtp = tp;
  246.         tp = (Tuple) ecalloct(sizeof(char *), (unsigned) n+1,
  247.           "tup-new-smalloc-exp");
  248.         tp[0] = (char *)n;
  249.         tp[1] = oldtp[1];
  250.         oldtp[0] = FREE_TUPLE; /* add smalloc block to free list */
  251.         FREE_TUPLE = (char *) oldtp;
  252.     }
  253.     else {
  254.         if ((unsigned)tp[0] >= n) return tp;
  255.         oldn = (unsigned)tp[0]+1;
  256.         tp[0] = (char *)n;
  257.         tp = (Tuple) erealloct((char *) tp, sizeof(char **) *((unsigned) n + 1),
  258.           "tup-exp");
  259.         for (; oldn <= n; oldn++)
  260.             tp[oldn] = (char *) 0;
  261.     }
  262.     return tp;
  263. }
  264.  
  265. void tup_free(Tuple tp)                                        /*;tup_free*/
  266. {
  267.     if (tp == NULL_TUPLE) return;
  268. #ifndef SMALLOC
  269.     efreet((char *) tp, "tup-free");
  270. #else
  271.     /* if tuple is allocated in smalloc area add to free list, otherwise
  272.      * free in usual way */
  273.     if (is_smalloc_block((char *) tp)) {
  274.         tp[0] = FREE_TUPLE;
  275.         FREE_TUPLE = (char *) tp;
  276.     }
  277.     else {
  278.         if (tp == NULL_TUPLE) return;
  279.         efreet((char *) tp, "tup-free");
  280.     }
  281. #endif
  282. }
  283.  
  284. char   *tup_frome(Tuple tp)                                    /*;tup_frome*/
  285. {
  286.     /* remove element from end */
  287.  
  288.     if ((int) tp[0] == 0) chaos("tup_frome: tuple already empty");
  289.     tp[0] -= 1;
  290.     return (tp[((int) tp[0]) + 1]);
  291. }
  292.  
  293. char   *tup_fromb(Tuple tp)                                    /*;tup_fromb*/
  294. {
  295.     /* remove element from front */
  296.  
  297.     int        n, i;
  298.     char   *elt;
  299.  
  300.     n = (int) tp[0];
  301.     if (n == 0) return 0;
  302.     elt = tp[1];
  303.     for (i = 2; i <= n; i++) 
  304.         tp[i - 1] = tp[i];
  305.     tp[0] = (char *) n-1; /* decrement length */
  306.     return elt;
  307. }
  308.  
  309. int   tup_mem(char *n, Tuple tp)                                /*;tup_mem*/
  310. {
  311.     int i;
  312.     int sz;
  313.  
  314.     if (tp == (Tuple)0) chaos("tup_mem: tuple not defined");
  315.  
  316.     sz = tup_size(tp);
  317.     if (sz<0 || sz >9999) chaos("tup_mem: ridiculous tuple element count");
  318.  
  319.     for (i = 1; i <= sz; i++) 
  320.         if (tp[i]== n) return TRUE;
  321.     return FALSE;
  322. }
  323.  
  324. int    tup_memi(char *n, Tuple tp)                                /*;tup_memi*/
  325. {
  326.     /* like tup_mem but returns index where n present, else 0 if n not present*/
  327.  
  328.     int    i, sz;
  329.  
  330.     sz = tup_size(tp);
  331.     for (i = 1; i <= sz; i++) 
  332.         if (tp[i] == n) return i;
  333.     return 0;
  334. }
  335.  
  336. int   tup_memstr(char *n, Tuple tp)                            /*;tup_memstr*/
  337. {
  338.     /* like tup_mem, but n is string, so use streq to check for equality*/
  339.  
  340.     int i;
  341.     int sz;
  342.  
  343.     sz = tup_size(tp);
  344.     for (i = 1; i <= sz; i++) 
  345.         if (strcmp(tp[i], n) == 0) return TRUE;
  346.     return FALSE;
  347. }
  348.  
  349. Tuple tup_new(int n)                                            /*;tup_new*/
  350. {
  351.     /* allocate new tuple with room for n elements */
  352.  
  353.     Tuple tp;
  354.  
  355.     if(n == 0) return NULL_TUPLE;
  356. #ifndef SMALLOC
  357.     tp = (Tuple) ecalloct( (unsigned) n + 1, sizeof(char **), "tup-new");
  358. #else
  359.     /* allocate via smalloc if length one */
  360.     if (n == 1) {
  361.         if (FREE_TUPLE != (char *)0) { /* if can take from free list */
  362.             tp = (Tuple) FREE_TUPLE;
  363.             FREE_TUPLE = (char *) tp[0];
  364.         }
  365.         else
  366.             tp= (Tuple) smalloc(2*sizeof(char *));
  367.         tp[1] = (char *)0; /* clear value */
  368.     }
  369.     else
  370.         tp = (Tuple) ecalloct( (unsigned) n + 1, sizeof(char **), "tup-new");
  371. #endif
  372.     tp[0] = (char *)n;
  373.     return tp;
  374. }
  375.  
  376. Tuple tup_new1(char *a)                                            /*;tup_new1*/
  377. {
  378.     Tuple tp;
  379.  
  380.     tp = tup_new(1);
  381.     tp[1] = a;
  382.     return (tp);
  383. }
  384.  
  385. Tuple tup_new2(char *a, char *b)                                /*;tup_new2*/
  386. {
  387.     Tuple tp;
  388.  
  389.     tp = tup_new(2);
  390.     tp[1] = a;
  391.     tp[2] = b;
  392.     return (tp);
  393. }
  394.  
  395. #ifndef EXPORT
  396. int    tup_size(Tuple tp)                                            /*;tup_size*/
  397. {
  398. #ifdef CHAOS
  399.     int n;
  400.  
  401.     if (tp == (Tuple)0) chaos("tup_size argument null pointer");
  402.  
  403.     n = (int)tp[0];
  404.     if (n < 0 || n > 99999) chaos("tup_size: size out of range");
  405. #endif
  406.     return (int) tp[0];
  407. }
  408. #endif
  409.  
  410. Tuple tup_with(Tuple tp, char *val)                                /*;tup_with*/
  411. {
  412.     /* add val at end of tuple, return pointer to result */
  413.  
  414.     unsigned    n;
  415.  
  416.     n = (unsigned) tp[0] + 1;
  417.     tp = tup_exp(tp, n);
  418.     tp[n] = (char *) val;
  419.     return tp;
  420. }
  421.  
  422. Set set_diff(Set sp1, Set sp2)                                    /*;set_diff*/
  423. {
  424.     /* return set of elements from sp1 that are not in sp2 */
  425.     Forset fs;
  426.     char *item;
  427.     Set spr;
  428.  
  429.     spr=set_new(0);
  430.     FORSET(item=(char *), sp1, fs);
  431.         if (!set_mem(item, sp2))
  432.             spr = set_with(spr, item);
  433.     ENDFORSET(fs);
  434.     return spr;
  435. }
  436.  
  437. #ifdef DEBUG
  438. void set_print(Set sp)                                            /*;set_print*/
  439. {
  440.     int        i, cur;
  441.  
  442.     cur = (int) sp[0];
  443.     for (i = 1; i <= cur; i++)
  444.         printf("%d%c", sp[i], (i ) % 10 ? ' ' : '\n');
  445.     if ((i ) % 10)
  446.         printf("\n");
  447. }
  448.  
  449. void tup_print(Tuple tp)                                        /*;tup_print*/
  450. {
  451.     /* print tuple on standard output */
  452.  
  453.     int        i;
  454.  
  455.     for (i = 1; i <= (int) tp[0]; i++)
  456.         printf("%d ", tp[i]);
  457.     printf("\n");
  458. }
  459. #endif
  460.